package com.tachoknight.geocaching.tsp;

import java.util.ArrayList;
import java.util.List;

import com.tachoknight.geocaching.Waypoint;

public class NearestNeighbor
{
	private List<Waypoint> waypoints;

	public NearestNeighbor(List<Waypoint> waypoints)
	{
		this.waypoints = waypoints;
	}

	public List<Waypoint> getSortedWaypoints()
	{
		assert (waypoints.size() > 2);

		List<Waypoint> sortedWaypoints = new ArrayList<Waypoint>();

		Waypoint initialWP = waypoints.get(0);
		sortedWaypoints.add(initialWP);
		waypoints.remove(0);
		boolean firstPass = true;
		Waypoint testWP = null;
		while (waypoints.size() > 0)
		{
			if (firstPass)
			{
				testWP = initialWP;
				firstPass = false;
			}

			Waypoint closestWP = testWP.isClosestTo(waypoints);
			sortedWaypoints.add(closestWP);
			waypoints.remove(closestWP);
			testWP = closestWP;
		}

		return sortedWaypoints;
	}
}
